1. Field of the Invention
The present invention relates generally to load balancing among network interfaces and more particularly to load-balancing in an LAG (Link Aggregation Group or a trunk), Weighted Cost Multipath Routing (WCMP) and Transparent Interconnection of Lots of Links (TRILL).
2. Description of Related Art
LAG, described in IEEE Standard 802.3ad, is a network data transmission method which groups a number of physical links or ports into a single logical entity and treats the physical links or ports as one single logical entity. The logical entity is called an LAG, a physical link or port is called an LAG member, and network traffic is distributed among the LAG members. As shown in FIG. 1, physical ports of a device may be divided into N logical groups (e.g., LAG 0, LAG 1, . . . LAG N−1), and each LAG may include m ports (e.g., 0-15). By combining several physical links or ports together, an LAG may increase data transmission speed, and provide redundancy.
Weighted-cost multi-path routing (WCMP) is a routing strategy where next-hop packet forwarding to a single destination can occur over multiple “best paths” which tie for top place in routing metric calculations. It potentially offers substantial increases in bandwidth by load-balancing traffic over multiple paths
Transparent Interconnection of Lots of Links (TRILL) is a forwarding policy that provides shortest-path frame routing in Ethernet networks. In particular it supports load-splitting among multiple paths. The following discussion takes load balancing among LAG members as an example, but it equally applies to WCMP and TRILL applications as can be appreciated by an ordinarily skilled person in the art.
FIG. 1 illustrates a load-balancing method according to this approach, wherein the traffic is load-balanced among LAG members according to a set of weights. In the example shown, the LAG has 4 members, the weights are 1:2:4:8 for LAG members 0, 1, 2 and 3 respectively, and 15 LAG members may be used to realize the weights. In other words, for each 15 packets, one packet is required to go to LAG member 0, two packets are required to go to LAG member 1, four packets are required to go to LAG member 2, and eight packets are required to go to LAG member 3. As shown, at 101, a destination LAG of a packet may be determined from the packet header or the switch configuration. In the example shown, the LAG number is LAG 1. At 102, information about LAG 1 may be obtained from an LAG Attributes Table, e.g., the number m of LAG members that the LAG 1 has. In one example, m=15 and the LAG Member Table may accommodate up to 16 members. At 103, a hash index h may be generated from the header of the packet. In one example, the hash index's width may be 8 bits and its value may be between 0 and 255. At 104, a modulo operation may be performed to obtain the remainder of division of h by m, and the remainder may be used as an LAG member number. When h is between 0 and 255 and m=15, the remainder of division of h by m may change from 0 to 14. At 105, LAG members may be physically replicated proportionally to their weights, and LAG members 0-14 in the LAG Member Table may become one LAG member 0, two LAG member 1s, four LAG member 2s and eight LAG member 3s.
One problem with this approach is its small dynamic range of weights and ratio between weights, since the sum of the weights cannot exceed the number of LAG members an LAG has, which is 16 in this example. One way to increase the weight dynamic range would be to increase the number of members in the LAG. However, increasing the number of LAG members would require larger table. It may also make the modulo operation more complicated.